# class Solution:
#     def calcEquation(self, equations, values, queries):
#         hashtable={}
#         for index,t in enumerate(equations):
#             hashtable[t[0]+'.'+t[1]]=values[index]
#             hashtable[t[1]+'.'+t[0]]=1/values[index]
#             hashtable[t[0]+'.'+t[0]]=1.0
#             hashtable[t[1]+'.'+t[1]]=1.0
#         for index,t in enumerate(equations):
#             keys=list(hashtable.keys())
#             for i in keys:
#                 temp=i.split(".")
#                 if t[1]==temp[0]:
#                     hashtable[t[0]+'.'+temp[1]]=values[index]*hashtable[i]
#                     hashtable[temp[1]+'.'+t[0]]=1/(values[index]*hashtable[i])
#                 if t[0]==temp[1]:
#                     hashtable[t[1]+'.'+temp[0]]=1/(values[index]*hashtable[i])
#                     hashtable[temp[0]+'.'+t[1]]=values[index]*hashtable[i]
#         result=[]
#         print(hashtable)
#         for t in queries:
#             try:
#                 result.append(hashtable[t[0]+"."+t[1]])
#             except KeyError:
#                 result.append(-1.0)
#         return result


# s=Solution()
# print(s.calcEquation([["a","b"],["c","b"],["d","b"],["w","x"],["y","x"],["z","x"],["w","d"]],
# [2.0,3.0,4.0,5.0,6.0,7.0,8.0],
# [["a","c"],["b","c"],["a","e"],["a","a"],["x","x"],["a","z"]]))



class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        nodes={}
        for index,i in enumerate(equations):
            if i[0] in nodes:
                nodes[i[0]].append([i[1],values[index]])
            else:
                nodes[i[0]]=[[i[1],values[index]],[i[0],1]]
            if i[1] in nodes:
                nodes[i[1]].append([i[0],1/values[index]])
            else:
                nodes[i[1]]=[[i[0],1/values[index]],[i[1],1]]
        def bfs(q):
            visited={i:0 for i in nodes.keys()}
            stack=[[q[0],1]]
            while stack:
                node=stack.pop()
                try:
                    for n in nodes[node[0]]:
                        if visited[n[0]]==0:
                            if n[0]==q[1]:
                                return n[1]*node[1]
                            else:
                                stack.append([n[0],n[1]*node[1]])
                                visited[n[0]]=1
                except KeyError:
                    return -1.0
            return -1.0
        return [bfs(q) for q in queries]

'''
执行用时：
36 ms
, 在所有 Python3 提交中击败了
84.29%
的用户
内存消耗：
15.1 MB
, 在所有 Python3 提交中击败了
6.70%
的用户
'''
